{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Nodes in the Sub-Tree With the Same Label"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #hash-table #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #哈希表 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSubTrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子树中标签相同的节点数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵树（即，一个连通的无环无向图），这棵树由编号从 <code>0</code>&nbsp; 到 <code>n - 1</code> 的 n 个节点组成，且恰好有 <code>n - 1</code> 条 <code>edges</code> 。树的根节点为节点 <code>0</code> ，树上的每一个节点都有一个标签，也就是字符串 <code>labels</code> 中的一个小写字符（编号为 <code>i</code> 的 节点的标签就是 <code>labels[i]</code> ）</p>\n",
    "\n",
    "<p>边数组 <code>edges</code> 以 <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 的形式给出，该格式表示节点 <code>a<sub>i</sub></code> 和 <code>b<sub>i</sub></code> 之间存在一条边。</p>\n",
    "\n",
    "<p>返回一个大小为 <em><code>n</code></em> 的数组，其中 <code>ans[i]</code> 表示第 <code>i</code> 个节点的子树中与节点 <code>i</code> 标签相同的节点数。</p>\n",
    "\n",
    "<p>树 <code>T</code> 中的子树是由 <code>T</code> 中的某个节点及其所有后代节点组成的树。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/07/19/q3e1.jpg\" style=\"height: 321px; width: 441px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = \"abaedcd\"\n",
    "<strong>输出：</strong>[2,1,1,1,1,1,1]\n",
    "<strong>解释：</strong>节点 0 的标签为 'a' ，以 'a' 为根节点的子树中，节点 2 的标签也是 'a' ，因此答案为 2 。注意树中的每个节点都是这棵子树的一部分。\n",
    "节点 1 的标签为 'b' ，节点 1 的子树包含节点 1、4 和 5，但是节点 4、5 的标签与节点 1 不同，故而答案为 1（即，该节点本身）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/07/19/q3e2.jpg\" style=\"height: 321px; width: 381px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, edges = [[0,1],[1,2],[0,3]], labels = \"bbbb\"\n",
    "<strong>输出：</strong>[4,2,1,1]\n",
    "<strong>解释：</strong>节点 2 的子树中只有节点 2 ，所以答案为 1 。\n",
    "节点 3 的子树中只有节点 3 ，所以答案为 1 。\n",
    "节点 1 的子树中包含节点 1 和 2 ，标签都是 'b' ，因此答案为 2 。\n",
    "节点 0 的子树中包含节点 0、1、2 和 3，标签都是 'b'，因此答案为 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/07/19/q3e3.jpg\" style=\"height: 321px; width: 381px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = \"aabab\"\n",
    "<strong>输出：</strong>[3,2,1,1,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10^5</code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>,&nbsp;b<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>a<sub>i</sub> !=&nbsp;b<sub>i</sub></code></li>\n",
    "\t<li><code>labels.length == n</code></li>\n",
    "\t<li><code>labels</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-nodes-in-the-sub-tree-with-the-same-label](https://leetcode.cn/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-nodes-in-the-sub-tree-with-the-same-label](https://leetcode.cn/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n[[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]]\\n\"abaedcd\"', '4\\n[[0,1],[1,2],[0,3]]\\n\"bbbb\"', '5\\n[[0,1],[0,2],[1,3],[0,4]]\\n\"aabab\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "\n",
    "        for i, j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "            deg[i] += 1\n",
    "            deg[j] += 1\n",
    "        deg[0] += 1\n",
    "        \n",
    "        ans = [0] * n\n",
    "        con = [([0] * 26) for _ in range(n)]\n",
    "        queue = deque()\n",
    "        for idx, i in enumerate(deg):\n",
    "            if i == 1:\n",
    "                queue.append(idx)\n",
    "                con[idx][ord(labels[idx]) - 97] += 1\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            ans[node] = con[node][ord(labels[node]) - 97]\n",
    "            for i in g[node]:\n",
    "                deg[i] -= 1\n",
    "                if deg[i] == 1:\n",
    "                    queue.append(i)\n",
    "                    for j in g[i]:\n",
    "                        if ans[j] != 0:\n",
    "                            for k in range(26):\n",
    "                                con[i][k] += con[j][k]\n",
    "                    con[i][ord(labels[i]) - 97] += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        indegree = [0] * n\n",
    "        label = [[0] * 26 for _ in range(n)]\n",
    "        parent = [-1] * n\n",
    "        parent[0] = 0\n",
    "        nodeDict = collections.defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            nodeDict[i].append(j)\n",
    "            nodeDict[j].append(i)\n",
    "        \n",
    "        stack = [0]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            for i in nodeDict[cur]:\n",
    "                if parent[i] == -1:\n",
    "                    parent[i] = cur\n",
    "                    stack.append(i)\n",
    "                    indegree[cur] += 1\n",
    "               \n",
    "        ans = [1] * n\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:    stack.append(i)\n",
    "        \n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            ans[cur] += label[cur][ord(labels[cur]) - ord(\"a\")]\n",
    "            for i in range(26):\n",
    "                label[parent[cur]][i] += label[cur][i]\n",
    "            label[parent[cur]][ord(labels[cur]) - ord(\"a\")] += 1\n",
    "            indegree[parent[cur]] -= 1\n",
    "            if indegree[parent[cur]] == 0:  stack.append(parent[cur])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        indegree = [0] * n\n",
    "        label = [[0] * 26 for _ in range(n)]\n",
    "        parent = [-1] * n\n",
    "        parent[0] = 0\n",
    "        nodeDict = collections.defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            nodeDict[i].append(j)\n",
    "            nodeDict[j].append(i)\n",
    "        \n",
    "        stack = [0]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            for i in nodeDict[cur]:\n",
    "                if parent[i] == -1:\n",
    "                    parent[i] = cur\n",
    "                    stack.append(i)\n",
    "                    indegree[cur] += 1\n",
    "               \n",
    "        ans = [1] * n\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:    stack.append(i)\n",
    "        \n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            ans[cur] += label[cur][ord(labels[cur]) - ord(\"a\")]\n",
    "            for i in range(26):\n",
    "                label[parent[cur]][i] += label[cur][i]\n",
    "            label[parent[cur]][ord(labels[cur]) - ord(\"a\")] += 1\n",
    "            indegree[parent[cur]] -= 1\n",
    "            if indegree[parent[cur]] == 0:  stack.append(parent[cur])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        indegree = [0] * n\n",
    "        label = [[0] * 26 for _ in range(n)]\n",
    "        parent = [-1] * n\n",
    "        parent[0] = 0\n",
    "        nodeDict = collections.defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            nodeDict[i].append(j)\n",
    "            nodeDict[j].append(i)\n",
    "        \n",
    "        stack = [0]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            for i in nodeDict[cur]:\n",
    "                if parent[i] == -1:\n",
    "                    parent[i] = cur\n",
    "                    stack.append(i)\n",
    "                    indegree[cur] += 1\n",
    "               \n",
    "        ans = [1] * n\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:    stack.append(i)\n",
    "        \n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            ans[cur] += label[cur][ord(labels[cur]) - ord(\"a\")]\n",
    "            for i in range(26):\n",
    "                label[parent[cur]][i] += label[cur][i]\n",
    "            label[parent[cur]][ord(labels[cur]) - ord(\"a\")] += 1\n",
    "            indegree[parent[cur]] -= 1\n",
    "            if indegree[parent[cur]] == 0:  stack.append(parent[cur])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        indegree = [0] * n\n",
    "        label = [[0] * 26 for _ in range(n)]\n",
    "        parent = [-1] * n\n",
    "        parent[0] = 0\n",
    "        nodeDict = collections.defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            nodeDict[i].append(j)\n",
    "            nodeDict[j].append(i)\n",
    "        \n",
    "        stack = [0]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            for i in nodeDict[cur]:\n",
    "                if parent[i] == -1:\n",
    "                    parent[i] = cur\n",
    "                    stack.append(i)\n",
    "                    indegree[cur] += 1\n",
    "               \n",
    "        ans = [1] * n\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:    stack.append(i)\n",
    "        \n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            ans[cur] += label[cur][ord(labels[cur]) - ord(\"a\")]\n",
    "            for i in range(26):\n",
    "                label[parent[cur]][i] += label[cur][i]\n",
    "            label[parent[cur]][ord(labels[cur]) - ord(\"a\")] += 1\n",
    "            indegree[parent[cur]] -= 1\n",
    "            if indegree[parent[cur]] == 0:  stack.append(parent[cur])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        e=collections.defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            e[a].append(b)\n",
    "            e[b].append(a)\n",
    "        ans=[0]*n\n",
    "        father=[-1]*n\n",
    "        #d=dict()\n",
    "        def dfs(x,c):\n",
    "            if labels[x]==c and ans[x]!=0:\n",
    "                return ans[x]\n",
    "            k=0\n",
    "            for ii in e[x]:\n",
    "                if ii==0:\n",
    "                    continue\n",
    "                if father[ii]==-1:\n",
    "                    father[ii]=x\n",
    "                    k+=dfs(ii,c)\n",
    "                elif father[ii]==x:\n",
    "                    k+=dfs(ii,c)\n",
    "                elif father[ii]!=x:\n",
    "                    continue\n",
    "                else:\n",
    "                    continue\n",
    "            if c==labels[x]:\n",
    "                k+=1\n",
    "                ans[x]=k\n",
    "            #print(x,c,k)\n",
    "            return k  \n",
    "        for i in range(n):\n",
    "            dfs(i,labels[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\r\n",
    "        res = [0] * n \r\n",
    "        g = [[] for _ in range(n)]\r\n",
    "        for x, y in edges:\r\n",
    "            g[x].append(y)\r\n",
    "            g[y].append(x)\r\n",
    "        vis = [False] * n \r\n",
    "        def dfs(x: int, fa: int):\r\n",
    "            cnt = Counter()\r\n",
    "            for y in g[x]:\r\n",
    "                if y != fa:\r\n",
    "                    cnt += dfs(y, x) \r\n",
    "            cnt[labels[x]] += 1\r\n",
    "            res[x] = cnt[labels[x]]\r\n",
    "            return cnt\r\n",
    "        dfs(0, -1)\r\n",
    "        return res \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        flag = [0] * n\n",
    "        graph = defaultdict(list)\n",
    "        for start, end in edges:\n",
    "            graph[start].append(end)\n",
    "            graph[end].append(start)\n",
    "        result = [0] * n\n",
    "\n",
    "        def dfs(node):\n",
    "            flag[node] = 1\n",
    "            current_num = defaultdict(int)\n",
    "            for next_node in graph[node]:\n",
    "                if flag[next_node] == 0:\n",
    "                    temp_d = dfs(next_node)\n",
    "                    for key, value in temp_d.items():\n",
    "                        current_num[key] += value\n",
    "\n",
    "            current_num[labels[node]] += 1\n",
    "            result[node] = current_num[labels[node]]\n",
    "            return current_num\n",
    "\n",
    "        dfs(0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        # 构建邻接列表\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        # 使用 DFS 计算每个节点的子树信息\n",
    "        def dfs(node, parent):\n",
    "            # 创建一个长度为 26 的数组\n",
    "            counts = [0] * 26\n",
    "            index = ord(labels[node]) - ord('a')\n",
    "            # 对当前节点的标签 +1\n",
    "            counts[index] = 1\n",
    "\n",
    "            # 遍历所有的子节点\n",
    "            for child in graph[node]:\n",
    "                if child != parent:\n",
    "                    child_counts = dfs(child, node)\n",
    "                    for i in range(26):\n",
    "                        counts[i] += child_counts[i]\n",
    "\n",
    "            ans[node] = counts[index]\n",
    "            return counts\n",
    "\n",
    "        ans = [0] * n\n",
    "        dfs(0, -1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        res = [1] * n\n",
    "\n",
    "        g = [[] for _  in range(n)]\n",
    "\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        def dfs(node, pa):\n",
    "            nodepos = ord(labels[node]) - ord('a')\n",
    "            tmp = [0] * 26\n",
    "            for ch in g[node]:\n",
    "                if ch != pa:\n",
    "                    chtmp = dfs(ch, node)\n",
    "                    tmp = list(map(lambda x, y: x + y, chtmp, tmp))\n",
    "            # print(y)\n",
    "            tmp[nodepos] += 1\n",
    "            res[node] = tmp[nodepos]\n",
    "            return tmp\n",
    "        dfs(0, -1)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for e1, e2 in edges:\n",
    "            g[e1].append(e2)\n",
    "            g[e2].append(e1)\n",
    "        ans = [0] * n\n",
    "\n",
    "        # 返回的是i节点及子节点的字符统计情况\n",
    "        def dfs(i,pa):\n",
    "            cnt = Counter()\n",
    "            for xi in g[i]:\n",
    "                if xi != pa:\n",
    "                    cnt += dfs(xi, i)\n",
    "            cnt[labels[i]] += 1\n",
    "            ans[i] = cnt[labels[i]]\n",
    "            return cnt\n",
    "\n",
    "        dfs(0, None)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for e1, e2 in edges:\n",
    "            g[e1].append(e2)\n",
    "            g[e2].append(e1)\n",
    "        \n",
    "        ans = [0] * n\n",
    "        def f(i, fa):\n",
    "            cnt = Counter()\n",
    "            for nexi in g[i]:\n",
    "                if nexi != fa:\n",
    "                    cnti = f(nexi, i)\n",
    "                    cnt += cnti\n",
    "            cnt[labels[i]] += 1\n",
    "            ans[i] = cnt[labels[i]]\n",
    "            return cnt\n",
    "        f(0,-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for e1, e2 in edges:\n",
    "            g[e1].append(e2)\n",
    "            g[e2].append(e1)\n",
    "\n",
    "        ans = [0] * n\n",
    "        def f(i, fa):\n",
    "            cnt = Counter()\n",
    "            for nex in g[i]:\n",
    "                if nex != fa:\n",
    "                    nexc = f(nex, i)\n",
    "                    cnt += nexc\n",
    "            cnt[labels[i]] += 1\n",
    "            ans[i] = cnt[labels[i]]\n",
    "            return cnt\n",
    "        f(0, -1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        \n",
    "        self.labels = labels\n",
    "        self.adj = list()\n",
    "        for i in range(n):\n",
    "            self.adj.append(list())\n",
    "        \n",
    "\n",
    "        for edge in edges:\n",
    "            start, end = edge[0], edge[-1]\n",
    "            self.adj[start].append(end)\n",
    "            self.adj[end].append(start)\n",
    "\n",
    "        self.ans = [0] * n\n",
    "               \n",
    "        self.dfs(0,0)\n",
    "        \n",
    "        return self.ans\n",
    "        \n",
    "    \n",
    "    def merge(self, a : List[int] , b: List[int]):\n",
    "        \n",
    "        for i in range(len(a)):\n",
    "            a[i]  += b[i]\n",
    "        \n",
    "       \n",
    "\n",
    "\n",
    "    def dfs(self, i: int, p: int) -> List[int]:\n",
    "\n",
    "        ret = [0] * 26\n",
    "              \n",
    "        ret[ord(self.labels[i]) - ord('a')] = 1 \n",
    "        if len(self.adj[i]) == 0:\n",
    "            self.ans[i] = 1\n",
    "            # print(f\"{i=} {labels[i]} {ret=}\")\n",
    "           \n",
    "            return ret     \n",
    "                       \n",
    "        \n",
    "        for  next in self.adj[i]:\n",
    "            if next == p:\n",
    "                continue\n",
    "            summary = self.dfs(next , i)\n",
    "            self.merge(ret, summary)\n",
    "\n",
    "        # print(f\"{i=} {labels[i]} {ret=}\")\n",
    "        self.ans[i] = ret[ord(self.labels[i]) - ord('a')] \n",
    "        return ret \n",
    "        \n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        dfs返回一个int[26] 保存子节点的标签信息\n",
    "        父节点需要累加子节点的标签信息并往上返回\n",
    "    '''\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        res = [0] * n\n",
    "        g = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        def dfs(x: int, fa: int) -> List[int]:\n",
    "            cur = [0] * 26\n",
    "            pos = ord(labels[x]) - ord('a')\n",
    "            cur[pos] += 1\n",
    "            for y in g[x]:\n",
    "                if y == fa: continue\n",
    "                # 子树的标签信息\n",
    "                child = dfs(y, x)\n",
    "                for i in range(26):\n",
    "                    cur[i] += child[i]\n",
    "            res[x] = cur[pos]\n",
    "            return cur\n",
    "        dfs(0, -1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,cur,parent,graph,labels):\n",
    "        d=defaultdict(int)\n",
    "        d[labels[cur]]+=1\n",
    "        for nei in graph[cur]:\n",
    "            if(nei!=parent):\n",
    "                d1=self.dfs(nei,cur,graph,labels)\n",
    "                for k,v in d1.items():\n",
    "                    d[k]+=d1[k]\n",
    "        self.res[cur]=d[labels[cur]]\n",
    "        return d\n",
    "                \n",
    "        \n",
    "    \n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        graph=defaultdict(list)\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "            \n",
    "        self.res=[0]*n\n",
    "        self.dfs(0,-1,graph,labels)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        ans = [0] * n\n",
    "        def dfs(u, fa):\n",
    "            ret = [0] * 26\n",
    "            for v in g[u]:\n",
    "                if v == fa: continue\n",
    "                cnt = dfs(v, u)\n",
    "                ret = [a + b for a, b in zip(ret, cnt)]\n",
    "            ret[ord(labels[u]) - ord('a')] += 1\n",
    "            ans[u] = ret[ord(labels[u]) - ord('a')]\n",
    "            return ret\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        roots = [[] for _ in range(n)]\n",
    "        for e in edges:\n",
    "            roots[e[0]].append(e[1])\n",
    "            roots[e[1]].append(e[0])\n",
    "        \n",
    "        from collections import Counter\n",
    "        visited = set()\n",
    "        dic = {}\n",
    "        res = [0]*n\n",
    "        def dfs(node):\n",
    "            visited.add(node)\n",
    "            dic = Counter({labels[node]:1})\n",
    "            for r in roots[node]:\n",
    "                if r not in visited:\n",
    "                    dic += dfs(r)\n",
    "            res[node] = dic[labels[node]]\n",
    "            return dic\n",
    "\n",
    "        dfs(0)\n",
    "        return res\n",
    "            \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        ans = [0] * n\n",
    "        def dfs(u, pa):\n",
    "            nonlocal ans\n",
    "            res = defaultdict(int)\n",
    "            res[labels[u]] += 1\n",
    "            for v in g[u]:\n",
    "                if v != pa:\n",
    "                    d = dfs(v, u)\n",
    "                    for x in d:\n",
    "                        res[x] += d[x]\n",
    "            ans[u] = res[labels[u]]\n",
    "            # print(u, res)\n",
    "            return res \n",
    "        \n",
    "        g = [[] for i in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        dfs(0, -1)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        G = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            G[u].append(v)\n",
    "            G[v].append(u)\n",
    "        ans = [0] * n\n",
    "\n",
    "        def dfs(u, p):\n",
    "            t = [0] * 26\n",
    "            t[ord(labels[u]) - ord('a')] = 1\n",
    "            for v in G[u]:\n",
    "                if v == p: continue\n",
    "                for i,x in enumerate(dfs(v,u)):\n",
    "                    t[i] +=x\n",
    "            ans[u] = t[ord(labels[u]) - ord('a')]\n",
    "            return t\n",
    "\n",
    "        dfs(0, -1)\n",
    "        del G\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        # 简单的后续遍历\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        def dfs(x, fa):\n",
    "            ch = ord(labels[x])-ord('a')\n",
    "            if g[x] == [fa]: \n",
    "                return [int(ch==i) for i in range(26)]\n",
    "            ans = [int(ch==i) for i in range(26)]\n",
    "            for child in g[x]:\n",
    "                if child != fa:\n",
    "                    cnt = dfs(child, x)\n",
    "                    for i, v in enumerate(cnt):\n",
    "                        ans[i] += v\n",
    "            res[x] = ans[ch]\n",
    "            return ans\n",
    "        \n",
    "        res = [1] * n\n",
    "        dfs(0, -1)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        ans=[0]*n \n",
    "        dct=[[]for i in range(n)]\n",
    "        for a,b in edges:\n",
    "            dct[a].append(b)\n",
    "            dct[b].append(a)\n",
    "        \n",
    "        def dfs(r,p):\n",
    "            res=[0]*26\n",
    "            res[ord(labels[r])-ord('a')]=1\n",
    "            for y in dct[r]:\n",
    "                if y==p:\n",
    "                    continue \n",
    "                x=dfs(y,r)\n",
    "                for i in range(26):\n",
    "                    res[i]+=x[i]\n",
    "            ans[r]=res[ord(labels[r])-ord('a')]\n",
    "            return res \n",
    "        dfs(0,-1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        ans = [1] * n\n",
    "        g[0].append(-1)\n",
    "        def dfs(x, fa):\n",
    "            arr = [0] * 26\n",
    "            if len(g[x]) == 1:\n",
    "                arr[ord(labels[x]) - ord('a')] += 1\n",
    "                return arr\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    childArr = dfs(y, x)\n",
    "                    # print(y,x,childArr)\n",
    "                    for i in range(26):\n",
    "                        arr[i] += childArr[i]\n",
    "            # print(x,arr)\n",
    "            ans[x] = arr[ord(labels[x]) - ord('a')] + 1\n",
    "            arr[ord(labels[x]) - ord('a')] += 1\n",
    "            return arr\n",
    "\n",
    "        dfs(0, -1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\r\n",
    "        res = [0] * n \r\n",
    "        g = [[] for _ in range(n)]\r\n",
    "        for x, y in edges:\r\n",
    "            g[x].append(y)\r\n",
    "            g[y].append(x)\r\n",
    "        vis = [False] * n \r\n",
    "        def dfs(x: int, fa: int):\r\n",
    "            cnt = [0] * 26\r\n",
    "            for y in g[x]:\r\n",
    "                if y != fa:\r\n",
    "                    ry = dfs(y, x) \r\n",
    "                    for i in range(26):\r\n",
    "                        cnt[i] += ry[i]\r\n",
    "            cnt[ord(labels[x]) - ord('a')] += 1\r\n",
    "            res[x] = cnt[ord(labels[x]) - ord('a')]\r\n",
    "            return cnt\r\n",
    "        dfs(0, -1)\r\n",
    "        return res \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        nums = [ord(ch) - 97 for ch in labels]\n",
    "\n",
    "        ans = [0] * n\n",
    "        def dfs(x, pa):\n",
    "            res = [0] * 26\n",
    "            res[nums[x]] += 1\n",
    "            for y in g[x]:\n",
    "                if y != pa:\n",
    "                    for i, c in enumerate(dfs(y, x)):\n",
    "                        res[i] += c\n",
    "            ans[x] = res[nums[x]]\n",
    "            return res\n",
    "\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        dic={}\n",
    "        ad={i:[] for i in range(n)}\n",
    "\n",
    "  \n",
    "        for s,e in edges:\n",
    "            ad[s].append(e)\n",
    "            ad[e].append(s)\n",
    "        ans=[1]*n\n",
    "        def dfs(cur,fa):\n",
    "            data = Counter({labels[cur]: 1})\n",
    "            for nex in ad[cur]:\n",
    "                if nex != fa:\n",
    "                    data+=dfs(nex,cur)\n",
    "            ans[cur] = data[labels[cur]]\n",
    "            return data\n",
    "        dfs(0, 0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        from collections import Counter\n",
    "\n",
    "        edge_map = defaultdict(list)\n",
    "        for edge in edges:\n",
    "            edge_map[edge[0]].append(edge[1])\n",
    "            edge_map[edge[1]].append(edge[0])\n",
    "\n",
    "        def _dfs(i):\n",
    "            visited.add(i)\n",
    "            # 字符数字典\n",
    "            data = Counter({labels[i]: 1})\n",
    "            for nxt in edge_map[i]:\n",
    "                if nxt in visited: continue # 去重\n",
    "                # 整合子树的字符数\n",
    "                data += _dfs(nxt)\n",
    "            # 设置当前节点的结果字符数\n",
    "            ans[i] = data[labels[i]]\n",
    "            return data\n",
    "\n",
    "        visited = set()\n",
    "        ans = [1] * n\n",
    "        _dfs(0)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        from collections import Counter\n",
    "\n",
    "        edge_map = defaultdict(list)\n",
    "        for edge in edges:\n",
    "            edge_map[edge[0]].append(edge[1])\n",
    "            edge_map[edge[1]].append(edge[0])\n",
    "\n",
    "        def _dfs(i):\n",
    "            visited.add(i)\n",
    "            # 字符数字典\n",
    "            data = Counter({labels[i]: 1})\n",
    "            for nxt in edge_map[i]:\n",
    "                if nxt in visited: continue # 去重\n",
    "                # 整合子树的字符数\n",
    "                data += _dfs(nxt)\n",
    "            # 设置当前节点的结果字符数\n",
    "            ans[i] = data[labels[i]]\n",
    "            return data\n",
    "\n",
    "        visited = set()\n",
    "        ans = [1] * n\n",
    "        _dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        from collections import Counter\n",
    "\n",
    "        edge_map = defaultdict(list)\n",
    "        for edge in edges:\n",
    "            edge_map[edge[0]].append(edge[1])\n",
    "            edge_map[edge[1]].append(edge[0])\n",
    "\n",
    "        def _dfs(i):\n",
    "            visited.add(i)\n",
    "            # 字符数字典\n",
    "            data = Counter({labels[i]: 1})\n",
    "            for nxt in edge_map[i]:\n",
    "                if nxt in visited: continue # 去重\n",
    "                # 整合子树的字符数\n",
    "                data += _dfs(nxt)\n",
    "            # 设置当前节点的结果字符数\n",
    "            ans[i] = data[labels[i]]\n",
    "            return data\n",
    "\n",
    "        visited = set()\n",
    "        ans = [1] * n\n",
    "        _dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class tree:\n",
    "    def __init__(self, id, label):\n",
    "        self.id=id\n",
    "        self.label=label\n",
    "        self.childnum=0\n",
    "        self.child=[]\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, n:int, graph, labels:str):\n",
    "        root=tree(0, labels[0])\n",
    "        visit=[0]*n\n",
    "        visit[0]=1\n",
    "        q=[root]\n",
    "        while q:\n",
    "            t=q.pop(0)\n",
    "            for neighbor in graph[t.id]:\n",
    "                if visit[neighbor]==0:\n",
    "                    visit[neighbor]=1\n",
    "                    neighbortree=tree(neighbor, labels[neighbor])\n",
    "                    t.child.append(neighbortree)\n",
    "                    t.childnum+=1\n",
    "                    q.append(neighbortree)\n",
    "        return root\n",
    "    \n",
    "    def dfs(self, root:tree, res:list[int], rootlabel:int, rootid:int):\n",
    "        if not root:\n",
    "            return\n",
    "        if root.label==rootlabel:\n",
    "            res[rootid]+=1\n",
    "            return\n",
    "        for ch in root.child:\n",
    "            self.dfs(ch, res, rootlabel, rootid)\n",
    "        \n",
    "    def preorder(self, root:tree, res:list[int]):\n",
    "        if not root:\n",
    "            return\n",
    "        self.dfs(root, res, root.label, root.id)\n",
    "        for ch in root.child:\n",
    "            self.preorder(ch, res)\n",
    "        \n",
    "        \n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        graph=collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        \n",
    "        visit=set()\n",
    "        res=[1]*n\n",
    "        def dfs(i):\n",
    "            visit.add(i)\n",
    "            data=collections.Counter({labels[i]:1})\n",
    "            for nxt in graph[i]:\n",
    "                if nxt in visit:\n",
    "                    continue\n",
    "                data+=dfs(nxt)\n",
    "            res[i]=data[labels[i]]\n",
    "            return data\n",
    "        \n",
    "        dfs(0)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        def dfs(node):\n",
    "            tmp = collections.Counter(labels[node])\n",
    "            children = ref[node]\n",
    "            for child in children:\n",
    "                if child not in vis:\n",
    "                    # print(child)\n",
    "                    vis.add(child)\n",
    "                    c_tmp = dfs(child)\n",
    "                    tmp+=c_tmp\n",
    "                    \n",
    "            res[node]+=tmp[labels[node]]\n",
    "            return tmp\n",
    "        \n",
    "        vis = set([0])\n",
    "        res = [0]*n\n",
    "        ref = collections.defaultdict(list)\n",
    "        for s,e in edges:\n",
    "            ref[e].append(s)\n",
    "            ref[s].append(e)\n",
    "        # print(ref)\n",
    "\n",
    "        dfs(0)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g=collections.defaultdict(list)\n",
    "        for i,j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        \n",
    "        ans=[0]*n\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            dic=collections.Counter(labels[i])\n",
    "            ans[i]=1\n",
    "            for x in g[i]:\n",
    "                if ans[x]==0:\n",
    "                    p=dfs(x)\n",
    "                    for k in p:\n",
    "                        if k in dic:\n",
    "                            dic[k]+=p[k]\n",
    "                        else:\n",
    "                            dic[k]=p[k]\n",
    "            ans[i]=dic[labels[i]]\n",
    "            return dic\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        ans = [0] * n\n",
    "\n",
    "        def dfs(x, fa):\n",
    "            cnt = Counter({labels[x]: 1})\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    cnt += dfs(y, x)\n",
    "            ans[x] = cnt[labels[x]]\n",
    "            return cnt\n",
    "\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        G = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            G[u].append(v)\n",
    "            G[v].append(u)\n",
    "        ans = [0] * n\n",
    "\n",
    "        def dfs(u, p):\n",
    "            t = [0] * 26\n",
    "            t[ord(labels[u]) - ord('a')] += 1\n",
    "            for v in G[u]:\n",
    "                if v == p: continue\n",
    "                t2 = dfs(v, u)\n",
    "                for i in range(26):\n",
    "                    t[i] += t2[i]\n",
    "            ans[u] = t[ord(labels[u]) - ord('a')]\n",
    "            return t\n",
    "\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        G = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            G[u].append(v)\n",
    "            G[v].append(u)\n",
    "        ans = [0] * n\n",
    "\n",
    "        def dfs(u, p):\n",
    "            t = [0] * 26\n",
    "            t[ord(labels[u]) - ord('a')] += 1\n",
    "            for v in G[u]:\n",
    "                if v == p: continue\n",
    "                # t2 = dfs(v, u)\n",
    "                # for i in range(26):\n",
    "                #     t[i] += t2[i]\n",
    "                for i,x in enumerate(dfs(v,u)):\n",
    "                    t[i] +=x\n",
    "            ans[u] = t[ord(labels[u]) - ord('a')]\n",
    "            return t\n",
    "\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        \n",
    "        self.labels = labels\n",
    "        self.adj = list()\n",
    "        for i in range(n):\n",
    "            self.adj.append(set())\n",
    "        \n",
    "\n",
    "        for edge in edges:\n",
    "            start, end = edge[0], edge[-1]\n",
    "            self.adj[start].add(end)\n",
    "            self.adj[end].add(start)\n",
    "\n",
    "        self.ans = [0] * n\n",
    "               \n",
    "        self.dfs(0,0)\n",
    "        \n",
    "        return self.ans\n",
    "        \n",
    "    \n",
    "    def merge(self, a : List[int] , b: List[int]):\n",
    "        \n",
    "        for i in range(len(a)):\n",
    "            a[i]  += b[i]\n",
    "        \n",
    "       \n",
    "\n",
    "\n",
    "    def dfs(self, i: int, p: int) -> List[int]:\n",
    "\n",
    "        ret = [0] * 26\n",
    "              \n",
    "        ret[ord(self.labels[i]) - ord('a')] = 1 \n",
    "        if len(self.adj[i]) == 0:\n",
    "            self.ans[i] = 1\n",
    "            # print(f\"{i=} {labels[i]} {ret=}\")\n",
    "           \n",
    "            return ret     \n",
    "                       \n",
    "        \n",
    "        for  next in self.adj[i]:\n",
    "            if next == p:\n",
    "                continue\n",
    "            summary = self.dfs(next , i)\n",
    "            self.merge(ret, summary)\n",
    "\n",
    "        # print(f\"{i=} {labels[i]} {ret=}\")\n",
    "        self.ans[i] = ret[ord(self.labels[i]) - ord('a')] \n",
    "        return ret \n",
    "        \n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        \n",
    "        self.labels = labels\n",
    "        self.adj = list()\n",
    "        for i in range(n):\n",
    "            self.adj.append(set())\n",
    "        \n",
    "\n",
    "        for edge in edges:\n",
    "            start, end = edge[0], edge[-1]\n",
    "            self.adj[start].add(end)\n",
    "            self.adj[end].add(start)\n",
    "\n",
    "        self.ans = [0] * n\n",
    "               \n",
    "        self.dfs(0,0)\n",
    "        \n",
    "        return self.ans\n",
    "        \n",
    "    \n",
    "    def merge(self, a : List[int] , b: List[int]):\n",
    "        \n",
    "        for i in range(len(a)):\n",
    "            a[i]  += b[i]\n",
    "        \n",
    "       \n",
    "\n",
    "\n",
    "    def dfs(self, i: int, p: int) -> List[int]:\n",
    "\n",
    "        ret = [0] * 26\n",
    "              \n",
    "        ret[ord(self.labels[i]) - ord('a')] = 1 \n",
    "        if len(self.adj[i]) == 0:\n",
    "            self.ans[i] = 1\n",
    "            # print(f\"{i=} {labels[i]} {ret=}\")\n",
    "           \n",
    "            return ret     \n",
    "                       \n",
    "        \n",
    "        for  next in self.adj[i]:\n",
    "            if next == p:\n",
    "                continue\n",
    "            summary = self.dfs(next , i)\n",
    "            self.merge(ret, summary)\n",
    "\n",
    "        # print(f\"{i=} {labels[i]} {ret=}\")\n",
    "        self.ans[i] = ret[ord(self.labels[i]) - ord('a')] \n",
    "        return ret \n",
    "        \n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        \n",
    "        self.labels = labels\n",
    "        self.adj = list()\n",
    "        for i in range(n):\n",
    "            self.adj.append(set())\n",
    "        \n",
    "\n",
    "        for edge in edges:\n",
    "            start, end = edge[0], edge[-1]\n",
    "            self.adj[start].add(end)\n",
    "            self.adj[end].add(start)\n",
    "\n",
    "        self.ans = [0] * n\n",
    "               \n",
    "        self.dfs(0,0)\n",
    "        \n",
    "        return self.ans\n",
    "        \n",
    "    \n",
    "    def merge(self, a : List[int] , b: List[int]):\n",
    "        \n",
    "        for i in range(len(a)):\n",
    "            a[i]  += b[i]\n",
    "        \n",
    "       \n",
    "\n",
    "\n",
    "    def dfs(self, i: int, p: int) -> List[int]:\n",
    "\n",
    "        ret = [0 for _ in range(26)]\n",
    "              \n",
    "        ret[ord(self.labels[i]) - ord('a')] = 1 \n",
    "        if len(self.adj[i]) == 0:\n",
    "            self.ans[i] = 1\n",
    "            # print(f\"{i=} {labels[i]} {ret=}\")\n",
    "           \n",
    "            return ret     \n",
    "                       \n",
    "        \n",
    "        for  next in self.adj[i]:\n",
    "            if next == p:\n",
    "                continue\n",
    "            summary = self.dfs(next , i)\n",
    "            self.merge(ret, summary)\n",
    "\n",
    "        # print(f\"{i=} {labels[i]} {ret=}\")\n",
    "        self.ans[i] = ret[ord(self.labels[i]) - ord('a')] \n",
    "        return ret \n",
    "        \n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        edge_map = defaultdict(list)\n",
    "        for edge in edges:\n",
    "            edge_map[edge[0]].append(edge[1])\n",
    "            edge_map[edge[1]].append(edge[0])\n",
    "\n",
    "        def _dfs(i):\n",
    "            nonlocal ans\n",
    "            visited.add(i)\n",
    "            # 字符数字典\n",
    "            data = Counter({labels[i]: 1})\n",
    "            for nxt in edge_map[i]:\n",
    "                if nxt in visited: continue\n",
    "                else: data += _dfs(nxt)\n",
    "            # 设置当前节点的结果字符数\n",
    "            ans[i] = data[labels[i]]\n",
    "            return data\n",
    "\n",
    "        visited = set()\n",
    "        ans = [1] * n\n",
    "        _dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        visited = set()\n",
    "        ans = [1] * n\n",
    "        def dfs(i):\n",
    "            visited.add(i)\n",
    "            data = Counter({labels[i] : 1})\n",
    "            \n",
    "            for nxt in graph[i]:\n",
    "                if nxt in visited:\n",
    "                    continue\n",
    "                data += dfs(nxt)\n",
    "            ans[i] = data[labels[i]]\n",
    "            \n",
    "            return data\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "\n",
    "        def add(a, b):\n",
    "            result = dict()\n",
    "            for k in a:\n",
    "                if k in b:\n",
    "                    result[k] = a[k] + b[k]\n",
    "                else:\n",
    "                    result[k] = a[k]\n",
    "            for k in b:\n",
    "                if k not in a:\n",
    "                    result[k] = b[k]\n",
    "            return result\n",
    "        \n",
    "        result = [0] * n\n",
    "        graph = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(root):\n",
    "            if root in visited:\n",
    "                return {}\n",
    "            visited.add(root)\n",
    "            counter = {labels[root]: 1}\n",
    "            for it in graph[root]:\n",
    "                counter = add(counter, dfs(it))\n",
    "            result[root] = counter[labels[root]]\n",
    "            return counter\n",
    "        \n",
    "        dfs(0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def dfs(node, pre):\n",
    "            f[node][ord(labels[node]) - ord(\"a\")] = 1\n",
    "\n",
    "            for next_node in g[node]:\n",
    "                if next_node != pre:\n",
    "                    dfs(next_node, node)\n",
    "                    for i in range(26):\n",
    "                        f[node][i] += f[next_node][i]\n",
    "        \n",
    "        f = [[0] * 26 for _ in range(n)]\n",
    "        dfs(0, -1)\n",
    "        ans = [f[i][ord(labels[i])-ord(\"a\")] for i in range(n)]\n",
    "\n",
    "        return ans\n",
    "             \n",
    "\n",
    "\n",
    "\n",
    "        # rs = [0]*n\n",
    "        # # print(rs)\n",
    "        # # 1. 构建树\n",
    "        # my_tree = dict()\n",
    "        # visited = set()\n",
    "        # node_list = [0]\n",
    "        # direct_kid_labels = dict()\n",
    "        # label_to_key_dict = dict()\n",
    "\n",
    "        # def dfs(node):\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # 以层序遍历的方式进行遍历\n",
    "        # while len(node_list) != 0:\n",
    "        #     key_node = node_list.pop()\n",
    "        #     if key_node not in my_tree.keys():\n",
    "        #         my_tree[key_node] = list()\n",
    "        #     kid_labels = []\n",
    "        #     edge_index_to_delete = []\n",
    "        #     for ei in range(len(edges)):\n",
    "        #         e = edges[ei]\n",
    "        #         if key_node in e:\n",
    "        #             other_node = None\n",
    "        #             if e[0] == key_node:\n",
    "        #                 other_node = e[1]\n",
    "        #             else:\n",
    "        #                 other_node = e[0]\n",
    "        #             if other_node in visited:\n",
    "        #                 continue\n",
    "                    \n",
    "        #             my_tree[key_node].append(other_node)\n",
    "        #             node_list.append(other_node)\n",
    "        #             kid_labels.append(labels[other_node])\n",
    "        #             edge_index_to_delete.append(ei)\n",
    "        #     edge_index_to_delete.sort(reverse=True)\n",
    "        #     for ei in edge_index_to_delete:\n",
    "        #         del edges[ei]\n",
    "\n",
    "        #     visited.add(key_node)\n",
    "        #     direct_kid_labels[key_node] = kid_labels\n",
    "        \n",
    "        # # 以遍历形式分别找各个节点的相同 label 节点个数\n",
    "        # for i in range(n):\n",
    "        #     count = 1 + direct_kid_labels[i].count(labels[i])\n",
    "\n",
    "        #     node_list = my_tree[i].copy()\n",
    "        #     while len(node_list) != 0:\n",
    "        #         key_node = node_list.pop()\n",
    "        #         node_list.extend(my_tree[key_node])\n",
    "        #         count += direct_kid_labels[key_node].count(labels[i])\n",
    "        #     rs[i] = count\n",
    "        # return rs\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "                    \n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def dfs(x, p):\n",
    "            f[x][ord(labels[x]) - ord('a')] = 1\n",
    "            for y in g[x]:\n",
    "                if y != p:\n",
    "                    dfs(y, x)\n",
    "                    for i in range(26):\n",
    "                        f[x][i] += f[y][i]\n",
    "\n",
    "        f = [[0] * 26 for _ in range(n)]\n",
    "\n",
    "        dfs(0, -1)\n",
    "        ans = [f[i][ord(labels[i]) - ord('a')] for i in range(n)]\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)      #构建字典\n",
    "\n",
    "        def dfs(o, pre):\n",
    "            f[o][ord(labels[o]) - ord('a')] = 1\n",
    "            for nex in g[o]:\n",
    "                if nex != pre:\n",
    "                    dfs(nex, o)\n",
    "                    for i in range(26):\n",
    "                        f[o][i] += f[nex][i]\n",
    "        \n",
    "        f = [[0]*26 for _ in range(n)]\n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = [f[i][ord(labels[i])  - ord('a')] for i in range(n)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        map = defaultdict(list)\n",
    "        cha = set()\n",
    "        for x, y in edges:\n",
    "            map[y].append(x)\n",
    "            map[x].append(y)\n",
    "        ans = [[0] * 26 for _ in range(n)]\n",
    "        def dfs(node, pre):\n",
    "            ans[node][ord(labels[node]) - ord('a')] = 1\n",
    "            for i in map[node]:\n",
    "                if i != pre:\n",
    "                    dfs(i, node)\n",
    "                    for x in range(26):\n",
    "                        ans[node][x] += ans[i][x]\n",
    "        dfs(0, -1)\n",
    "        res = [ans[i][ord(labels[i]) - ord('a')] for i in range(n)]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dfs(o: int, pre: int):\n",
    "            f[o][ord(labels[o]) - ord(\"a\")] = 1\n",
    "            for nex in g[o]:\n",
    "                if nex != pre:\n",
    "                    dfs(nex, o)\n",
    "                    for i in range(26):\n",
    "                        f[o][i] += f[nex][i]\n",
    "\n",
    "        f = [[0] * 26 for _ in range(n)]\n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = [f[i][ord(labels[i]) - ord(\"a\")] for i in range(n)]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        f = [[0]*26 for _ in range(n)]\n",
    "        def dfs(x,fa):\n",
    "            f[x][ord(labels[x])-ord('a')] = 1\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y,x)\n",
    "                    for i in range(26):\n",
    "                        f[x][i] += f[y][i]\n",
    "        dfs(0,-1)\n",
    "        ans = [f[i][ord(labels[i])-ord('a')] for i in range(n)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        ans = []\n",
    "        cnt = [[0] * 26 for _ in range(n)]\n",
    "        def dfs(node, fa):\n",
    "            cur = ord(labels[node]) - ord('a')\n",
    "            cnt[node][cur] += 1\n",
    "            for nei in g[node]:\n",
    "                if nei != fa:\n",
    "                    dfs(nei, node)\n",
    "                    for j in range(26):\n",
    "                        cnt[node][j] += cnt[nei][j]\n",
    "        dfs(0, -1)\n",
    "        for i in range(n):\n",
    "            ans.append(cnt[i][ord(labels[i]) - ord('a')])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        sub = [[0]*26 for _ in range(n)]\n",
    "        \n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "        \n",
    "        def dfs(x, fa):\n",
    "            for y in dct[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "                    for i in range(26):\n",
    "                        sub[x][i] += sub[y][i]\n",
    "            sub[x][ord(labels[x])-ord(\"a\")] += 1\n",
    "            return \n",
    "        dfs(0, -1)\n",
    "        return [sub[x][ord(labels[x])-ord(\"a\")] for x in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        visited = set()\n",
    "        ans = [1] * n\n",
    "        # def dfs(i):\n",
    "        #     visited.add(i)\n",
    "        #     data = Counter({labels[i] : 1})\n",
    "            \n",
    "        #     for nxt in graph[i]:\n",
    "        #         if nxt in visited:\n",
    "        #             continue\n",
    "        #         data += dfs(nxt)\n",
    "        #     ans[i] = data[labels[i]]\n",
    "            \n",
    "        #     return data\n",
    "        # dfs(0)\n",
    "        # return ans\n",
    "        f = [[0] * 26 for _ in range(n)]\n",
    "        def dfs(x, pre):\n",
    "            f[x][ord(labels[x]) - ord('a')] = 1\n",
    "            for nex in graph[x]:\n",
    "                if nex != pre:\n",
    "                    dfs(nex, x)\n",
    "                    for i in range(26):\n",
    "                        f[x][i] += f[nex][i]\n",
    "\n",
    "        dfs(0, -1)\n",
    "        res = [f[i][ord(labels[i]) - ord('a')] for i in range(n)]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        roots = [[] for _ in range(n)]\n",
    "        for e in edges:\n",
    "            roots[e[0]].append(e[1])\n",
    "            roots[e[1]].append(e[0])\n",
    "        \n",
    "        visited = set()\n",
    "        store = [[0 for i in range(26)] for _ in range(n)]\n",
    "        res = [0]*n\n",
    "        def dfs(node):\n",
    "            visited.add(node)\n",
    "            store[node][ord(labels[node])-ord('a')] = 1\n",
    "            for r in roots[node]:\n",
    "                if r not in visited:\n",
    "                    dfs(r)\n",
    "                    for i in range(26):\n",
    "                        store[node][i] += store[r][i]\n",
    "            res[node] = store[node][ord(labels[node])-ord('a')]\n",
    "            \n",
    "        dfs(0)\n",
    "        return res\n",
    "\n",
    "        # from collections import Counter\n",
    "        # visited = set()\n",
    "        # dic = {}\n",
    "        # res = [0]*n\n",
    "        # def dfs(node):\n",
    "        #     visited.add(node)\n",
    "        #     #  initialize \n",
    "        #     dic = Counter({labels[node]:1})\n",
    "        #     for r in roots[node]:\n",
    "        #         if r not in visited:\n",
    "        #             dic += dfs(r)\n",
    "        #     res[node] = dic[labels[node]]\n",
    "        #     return dic\n",
    "\n",
    "        # dfs(0)\n",
    "        # return res\n",
    "            \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dfs(o: int, pre: int):\n",
    "            f[o][ord(labels[o]) - ord(\"a\")] = 1\n",
    "            for nex in g[o]:\n",
    "                if nex != pre:\n",
    "                    dfs(nex, o)\n",
    "                    for i in range(26):\n",
    "                        f[o][i] += f[nex][i]\n",
    "\n",
    "        f = [[0] * 26 for _ in range(n)]\n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = [f[i][ord(labels[i]) - ord(\"a\")] for i in range(n)]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dfs(o: int, pre: int):\n",
    "            f[o][ord(labels[o]) - ord(\"a\")] = 1\n",
    "            for nex in g[o]:\n",
    "                if nex != pre:\n",
    "                    dfs(nex, o)\n",
    "                    for i in range(26):\n",
    "                        f[o][i] += f[nex][i]\n",
    "\n",
    "        f = [[0] * 26 for _ in range(n)]\n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = [f[i][ord(labels[i]) - ord(\"a\")] for i in range(n)]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dfs(o: int, pre: int):\n",
    "            f[o][ord(labels[o]) - ord(\"a\")] = 1\n",
    "            for nex in g[o]:\n",
    "                if nex != pre:\n",
    "                    dfs(nex, o)\n",
    "                    for i in range(26):\n",
    "                        f[o][i] += f[nex][i]\n",
    "\n",
    "        f = [[0] * 26 for _ in range(n)]\n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = [f[i][ord(labels[i]) - ord(\"a\")] for i in range(n)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dfs(o: int, pre: int):\n",
    "            f[o][ord(labels[o]) - ord(\"a\")] = 1\n",
    "            for nex in g[o]:\n",
    "                if nex != pre:\n",
    "                    dfs(nex, o)\n",
    "                    for i in range(26):\n",
    "                        f[o][i] += f[nex][i]\n",
    "\n",
    "        f = [[0] * 26 for _ in range(n)]\n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = [f[i][ord(labels[i]) - ord(\"a\")] for i in range(n)]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dfs(o: int, pre: int):\n",
    "            f[o][ord(labels[o]) - ord(\"a\")] = 1\n",
    "            for nex in g[o]:\n",
    "                if nex != pre:\n",
    "                    dfs(nex, o)\n",
    "                    for i in range(26):\n",
    "                        f[o][i] += f[nex][i]\n",
    "\n",
    "        f = [[0] * 26 for _ in range(n)]\n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = [f[i][ord(labels[i]) - ord(\"a\")] for i in range(n)]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            \n",
    "        def dfs(o: int, pre: int):\n",
    "            f[o][ord(labels[o]) - ord(\"a\")] = 1\n",
    "            for nex in g[o]:\n",
    "                if nex != pre:\n",
    "                    dfs(nex, o)\n",
    "                    for i in range(26):\n",
    "                        f[o][i] += f[nex][i]\n",
    "\n",
    "        f = [[0] * 26 for _ in range(n)]\n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = [f[i][ord(labels[i]) - ord(\"a\")] for i in range(n)]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        arr=[[] for _ in range(n)]\n",
    "        \n",
    "        ff=[[0 for _ in range(26)] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            arr[edge[0]].append(edge[1])\n",
    "            arr[edge[1]].append(edge[0])\n",
    "        def dfs(x, y):\n",
    "            ff[x][ord(labels[x])-ord('a')]=1\n",
    "            for new_node in arr[x]:\n",
    "                if new_node==y:\n",
    "                    continue\n",
    "                dfs(new_node, x)\n",
    "                for i in range(26):\n",
    "                    ff[x][i]+=ff[new_node][i]\n",
    "        dfs(0, -1)\n",
    "        ans=[]\n",
    "        for i in range(n):\n",
    "            ans.append(ff[i][ord(labels[i])-ord('a')])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        # graph = [[] for _ in range(n)]\n",
    "        # #print(graph)\n",
    "        # res = [1] * n\n",
    "        # outdgree = [0] * n\n",
    "        # for u,v in edges:\n",
    "        #     graph[v].append(u)\n",
    "        #     outdgree[u] += 1\n",
    "        # qu = collections.deque([])\n",
    "        # for i in range(n):\n",
    "        #     if outdgree[i] == 0:\n",
    "        #         qu.append(i)\n",
    "        # while qu:\n",
    "        #     p = qu.popleft()\n",
    "        #     for u in graph[p]:\n",
    "        #         outdgree[u] -= 1\n",
    "        #         if labels[u] == labels[p]:\n",
    "        #             res[u] += res[p]\n",
    "        #         if outdgree[u] == 0:\n",
    "        #             qu.append(u)\n",
    "                    \n",
    "        # return res\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        def dfs(node:int,pre:int):\n",
    "            f[node][ord(labels[node])-ord('a')] = 1\n",
    "            for nex in graph[node]:\n",
    "                if nex != pre:\n",
    "                    dfs(nex,node)\n",
    "                    for i in range(26):\n",
    "                        f[node][i] += f[nex][i]\n",
    "\n",
    "        f = [[0]*26 for _ in range(n)]\n",
    "        print(f)\n",
    "        dfs(0,-1)\n",
    "\n",
    "        ans = [f[i][ord(labels[i]) - ord(\"a\")] for i in range(n)]\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        @cache\n",
    "        def dfs(o: int, pre: int):\n",
    "            f[o][ord(labels[o]) - ord(\"a\")] = 1\n",
    "            for nex in g[o]:\n",
    "                if nex != pre:\n",
    "                    dfs(nex, o)\n",
    "                    for i in range(26):\n",
    "                        f[o][i] += f[nex][i]\n",
    "\n",
    "        f = [[0] * 26 for _ in range(n)]\n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = [f[i][ord(labels[i]) - ord(\"a\")] for i in range(n)]\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
